package com.example.testsbjenkins.skipList;

import java.util.Random;

/**
 * @author: lt
 * @date: 2022/6/21 13:18
 * @Description: todo
 */
public class SkipList {
    
    
    //节点
    class SkipNode<T>{
        
        int key;
        T value;
        SkipNode right,down;//右下方向的指针

        public SkipNode(int key, T value) {
            this.key = key;
            this.value = value;
        }
    }
    SkipNode headNode;//头部节点
    int highLevel;//当前调表的索引层数
    Random random;//随机数
    static final int MAX_LEVEL = 32;//索引的最大层

    public SkipList() {
        this.headNode = new SkipNode(Integer.MIN_VALUE,null);
        this.highLevel = 0;
        this.random = new Random();
    }


    /**
     * 查询方法
     * @param key
     * @return
     */
    public SkipNode search(int key){
        SkipNode team = headNode;
        while (team != null){

            if (team.key == key) {//头结点找到了 就返回头结点
                return team;
            }else if (team.right == null){//右侧没有了 只能下降
                team = team.down;
            }else if (team.right.key>key){//右侧比要查的数据大 只能下降
                team = team.down;
                
            }else {//右侧数据比要查数据小 向右
                team =team.right;
            }
            
            
        }
        return null;
    }

    /**
     * 删除
     * @param key
     */
    public void delete(int key){
        SkipNode team = headNode;
        while (team != null){
            
            if (team.right == null){//右侧没有了 只能下降
                team = team.down;
            }else if (team.right.key == key){//找到节点，右侧即为待删除节点
                team.right=team.right.right;//删除右侧节点
                team=team.down;//向下继续查找删除
            }else if(team.right.key>key)//右侧已经不可能了，向下
            {
                team=team.down;
            }
            else { //节点还在右侧
                team=team.right;
            }
        }
    }
    
}
